package problem08_07;

import java.util.ArrayList;
import java.util.List;

//面试题08.07.无重复字符串的排列组合
//https://leetcode.cn/problems/permutation-i-lcci/description/

class Solution {
    boolean[] st;
    int n;
    List<String> ret;
    String str;
    public String[] permutation(String S) {
        str = S;
        n = str.length();
        st = new boolean[n];
        ret = new ArrayList<>();
        dfs(new StringBuffer());
        return ret.toArray(new String[ret.size()]);
    }

    public void dfs(StringBuffer s) {
        if(s.length() == n) {
            ret.add(new String(s));
        }
        for(int i = 0; i<n; i++) {
            if(!st[i]) {
                st[i] = true;
                s.append(str.charAt(i));
                dfs(s);
                s.deleteCharAt(s.length()-1);
                st[i] = false;
            }
        }
    }
}